package com.agile.leetcode.hot.middle;

import java.util.Arrays;

/**
 * 300. 最长递增子序列
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * <p>
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 * @Author:ChenZhangKun
 * @Date: 2021/5/29 16:46
 */
public class LengthOfLIS {
    public static void main(String[] args) {
        LengthOfLIS lis = new LengthOfLIS();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lis.lengthOfLIS(nums));
    }

    public int lengthOfLIS(int[] nums) {
        // 判断
        int len = nums.length;
        if (len < 2) {
            return len;
        }
        // 创建dp数组
        int[] dp = new int[len];
        // 全部置为1
        Arrays.fill(dp, 1);
        // 定义结果
        int result = dp[0];
        // 遍历数组
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                // 状态转移方程
                if (nums[i] > nums[j]) {
                    // 推导状态转移方程：遍历到 nums[i] 的时候，我们应该把下标区间 [0, ... ,i - 1] 的 dp 值都看一遍，
                    // 如果当前的数 nums[i] 大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。把前面的数都看了，
                    // dp[i] 就是它们的最大值加 $1$。即比当前数要小的那些里头，找最大的，然后加 $1$ 。
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

class Practice {
    public static void main(String[] args) {
        Practice lis = new Practice();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lis.lengthOfLIS(nums));
    }
    public int lengthOfLIS(int[] nums) {
        // 拿到长度
        int length = nums.length;
        if (length < 2) {
            // 此时只有一个元素
            return length;
        }
        // 创建数组
        int[] dp = new int[length];
        // 定义结果
        int result = dp[0];
        // 填充数组
        Arrays.fill(dp, 1);
        // 遍历
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}
